1. Field of the Invention
The present invention relates to block processing encoded data with a maximum a posteriori (MAP) algorithm by a receiver in a telecommunications system.
2. Description of the Related Art
MAP decoding algorithms are employed for processing data input to a processor for detection and/or decoding operations. The algorithm provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process. The MAP algorithm forms a trellis corresponding to possible states (determined by a portion of received symbol bits in the sequence) for each received channel output value per unit increment in time (i.e., clock cycle).
States, and transitions between states, of the Markov process spanning an interval of time may be represented by a trellis diagram. The number of bits that a state represents is equivalent to the memory of the Markov process. Thus, probabilities (sometimes of the form of log-likelihood values) are associated with each transition within the trellis, and probabilities are also associated with each decision for a symbol bit in the sequence.
The processor using the MAP algorithm computes log-likelihood values using α values (forward state probabilities for states in the trellis), and then β values (backward state probabilities in the trellis) after the α values are computed, as described subsequently. The α values are associated with states within the trellis, and these α values are stored in memory. The processor using the MAP algorithm computes values of β, and the α values are then retrieved from memory to compute the final output log-likelihood values. To compute the log-likelihood values, the entire state metric array of α values is stored by the MAP algorithm.
The variable Sk is defined as the set of states of the Markov process at time k, and yk is defined as the noisy channel output sample at time k, the sample sequence of length K=L+1 is defined as the sequence yK=(y0, y1, . . . , yk, . . . , yL) and, for a data block of length K, probability functions may be defined for the Markov process as given in equations (1) through (3):αsk=p(Sk=s; yks)  (1)βsk=p(yk+1K|Sk=s)  (2)γs′,sk=p(Sk=s; yk|Sk−1=s′).  (3)where s defines the state Sk of the Markov process at time k and s′ defines the state Sk−1 of the Markov process at time k−1.
The log-likelihood value L(uk) for a user's symbol uk at time k may then be calculated as given in equation (4):
                              L          ⁡                      (                          u              k                        )                          =                              log            ⁡                          (                                                p                  ⁡                                      (                                                                  u                        k                                            =                                                                        +                          1                                                |                                                  y                          k                          K                                                                                      )                                                                    p                  ⁡                                      (                                                                  u                        k                                            =                                                                        -                          1                                                |                                                  y                          k                          K                                                                                      )                                                              )                                .                                    (        4        )            
FIG. 1 shows an 8 state trellis from time k−2 to time k. In the figures, the number next to the state indicates the state number i.
Defining αlk and βlk from equations (1) and (2) as the forward and backward probabilities (state metrics) at time k in state i, respectively, and defining γl,jk as the branch metric associated with the transition from state i at time k−1 to state j at time k, then, the forward recursion for states is given in equation (5):
                                          a            j            k                    =                                    ∑                              i                ⁢                                                                  ⁢                ε                ⁢                                                                  ⁢                S                                      ⁢                                          α                i                                  k                  -                  1                                            ⁢                              γ                                  i                  ,                  j                                k                                                    ,                              for            ⁢                                                  ⁢            j                    =          0                ,        1        ,        …        ⁢                                  ,                  M          -          1.                                    (        5        )            where i∈S is a set of states at time k−1 which have a valid transition to the state j at time k, and M is the number of states.
Similarly, the backward recursion for states is given in equation (6):
                                          β            i                          k              -              1                                =                                    ∑                              j                ⁢                                                                  ⁢                ε                ⁢                                                                  ⁢                S                                      ⁢                                          β                j                k                            ⁢                              γ                                  i                  ,                  j                                k                                                    ,                              for            ⁢                                                  ⁢            i                    =          0                ,        1        ,        …        ⁢                                  ,                  M          -          1.                                    (        6        )            where j∈S is a set of states at time k which have a valid transition from the state i at time k−1.
Once the forward and backward recursions for states are calculated, from equation (4), the log-likelihood value (also known as reliability value) L(uk) for each user symbol uk is generated as given in equation (7):
                              L          ⁡                      (                          u              k                        )                          =                  log          ⁡                      (                                                            ∑                                                            (                                              i                        ,                        j                                            )                                        ⁢                    ε                    ⁢                                                                                  ⁢                                          S                      +                                                                      ⁢                                                      α                    i                                          k                      -                      1                                                        ⁢                                      γ                                          i                      ,                      j                                        l                                    ⁢                                      β                    j                    k                                                                                                ∑                                                            (                                              i                        ,                        j                                            )                                        ⁢                    ε                    ⁢                                                                                  ⁢                                          S                      -                                                                      ⁢                                                      α                    i                                          k                      -                      1                                                        ⁢                                      γ                                          i                      ,                      j                                        k                                    ⁢                                      β                    j                    k                                                                        )                                              (        7        )            where a state pair (i, j)∈S+ is defined as a pair that has a transition from state i at time k−1 to state j at time k corresponding to the user symbol uk=“1”, and a state pair (i, j)∈S− is similarly defined as a pair that has a transition from state i at time k−1 to state j at time k corresponding to the user symbol uk=“−1”.
The Log MAP algorithm may be defined by substituting Ajk=ln(αjk), Bjk=ln(βjk) and Γi,jk=ln(γl,jk) into the equations (5), (6), and (7). Also, with the relation that ln(exp x+exp y) is equivalent to max(x,y)+ln(exp(−|x−y|)+1), the Log MAP algorithm may be described as in equations (8) and (9):
                              A          j          k                =                              max                          i              ⁢                                                          ⁢              ε              ⁢                                                          ⁢              S                                ⁢                      *                          (                                                a                  i                                      k                    -                    1                                                  +                                  Γ                                      i                    ,                    j                                    k                                            )                                                          (        8        )                                          B          i                      k            -            1                          =                              max                          j              ⁢                                                          ⁢              ε              ⁢                                                          ⁢              S                                ⁢                      *                          (                                                B                  j                                      k                    -                    1                                                  +                                  Γ                                      i                    ,                    j                                    k                                            )                                                          (        9        )            where max*(x, y) is defined as max(x, y)+ln(exp(−|x−y|)+1).
As an example, for the forward recursion, A2k in state 2 at time k as shown in FIG. 1 is computed as in equation (10):A2k=max*(A1k−1+Γ1,2k, A5k−1+Γ5,2k).  (10)When implemented, a MAP algorithm updates the state metrics to compute αlk and βlk−1 (or their log values for the Log MAP algorithm) based on 1) the current values for the state metrics αik−1 and βlk for all i (all states in the set S) and 2) the current sample yk. The update occurs for each time k=0, 1, 2, . . . , L, and each update for time k performs a calculation using only the sample corresponding to time k. Thus, the read/write operation for an implementation transfers a single sample word for each update operation at a given rate f.